The present invention relates to a parallel computer comprising a plurality of processors constituting a network for transferring messages therebetween.
One of the capabilities required of the network of the parallel computer is a high throughput, i.e., the ability to transmit a large number of messages in a short time.
A majority of conventional parallel computers operate under what is known as the dimension ordered routing scheme for network routing. Dimension ordered routing involves transmitting all messages from, say, a one-dimensional direction to a two-dimensional direction in the same transfer procedure. The same applies when a path conflict occurs between different messages. In the case of such a conflict, the initially transmitted message is given priority in transfer over the subsequently transmitted message. Where dimension ordered routing is employed, a transfer route not actually used can develop on the network. In a conventional dimension ordered routing setup, messages may concentrate on a specific portion of the network or may not use certain routes at all. That is, part of the transfer routes on the network are not utilized effectively. Incidentally, the message conflict refers to cases where the transfer route of one message conflicts with that of another message so that one of the messages is delayed in transfer.
One solution to the above problem is the so-called adaptive routing disclosed in the Papers from Information Processing Society of Japan, Proc. of Symposium on Parallel Processing JSPP '94, pp. 129-136, May 1994 (hereafter referred to as the first-cited reference). The adaptive routing scheme attempts to disperse transfer routes of messages over the network by utilizing the routes effectively. The first-cited reference discusses cases in which adaptive routing is applied to a hyper-crossbar network.
The disclosed adaptive routing method works as follows: When a path conflict occurs as mentioned, the message later transmitted is transferred on the spot to a currently available route (in a different dimensional direction). This resolves the conflict state. By distributing messages to different transfer routes, the adaptive routing method utilizes all transfer routes on the network effectively and makes the load on each of the transfer routes as equally distributed as possible.
There is one major disadvantage to the network enabling a plurality of transfer routes to transfer messages to the same destination: there may occur a closed loop of a channel chain between a plurality of messages. That is, each of, say, two messages attempts to take over the transfer route of the other message, resulting in a deadlock. Illustratively, suppose that in a three-dimensional network situation, a message 1 is to be transmitted over routes X, Y and Z in that order while a message 2 is to be sent over routes Y, Z and X in that order. As the message 1 is trying to take the route Z and the message 2 the route X, a loop is formed between the two transfer routes leading to a deadlock. The Way to avoid the deadlock proposed in the first-cited reference involves using virtual channels on the hyper-crossbar network. Virtual channels are made up of a plurality of independent buffers (i.e., virtual channels) for storing messages with respect to each physical channel of the network. A plurality of virtual channels share one physical channel. The first-cited reference explains how the deadlock state is resolved by utilizing virtual channels on the hyper-crossbar network. What follows is a description of how virtual channels are used.
The hyper-crossbar network illustratively includes "in" processors, "n" being factorized into n1.times.n2.times.n3.times. . . . , nm. Each of the factors is regarded as a one-side mesh cross-point count constituting an m-dimensional mesh space in which processors are disposed. The sides of the mesh are connected by partial networks composed of crossbar switches so as to form message transfer routes. In this example, each crossbar switch is provided with as many buffers as the number of dimensions (m). One physical channel is used as "m" virtual channels. Illustratively, in the above-described three-dimensional network, an adaptive routing scheme based on virtual channels allows the message 1 to be transferred over routes X1, Y2 and Z3 in that order, and enable the message 2 to be moved through routes Y1, Z2 and X3 in that order (subscripts 1, 2 and 3 added to characters X, Y and Z indicate virtual channel numbers). This prevents any closed loop from developing between the routes thereby avoiding deadlock. In this example, it is possible to select any dimension when each crossbar switch is transited provided the selected dimension has not been passed through in the past.
Virtual channels are allocated depending on the number of crossbar switches transited so far by the message in question. Each message contains therein dynamic transfer route transit information (describing, among others, which switches the message in question has transited so far) in order to suppress deadlock.
The concept of virtual channels was proposed earlier in IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, Vol. 3, No. 2, pp. 194-205, March 1992 (hereafter called the second-cited reference). This reference also indicates that the deadlock state is avoided by applying virtual channels to a torus network based on dimension ordered routing.
Another capability required of the network of the parallel computer is a minimized possibility of conflict between different types of messages. These types of messages transferred over the network of the parallel computer include broadcast messages, synchronization messages, data transfer messages and emergency messages and so on. They vary in type depending on the purpose. If a conflict occurs between such different types of messages, one of the messages (e.g., emergency message) can be delayed in transfer.
Some parallel computers have a plurality of message-wise networks for the efficient transfer of messages differing in their purposes. For example, the parallel computer introduced in Information Processing Society of Japan, IPSJ SIG Notes ARC, Vol. 92, No. 64, pp. 89-96 (hereafter called the third-cited reference) have three independent networks: one for broadcast messages, another for synchronization messages and another for data transfer messages.
Japanese Patent Laid-Open No. Sho 63-124162 (hereafter called the fourth-cited reference) discloses a technique whereby, in case of a fault on the network, the current message transfer route is switched so as to bypass the faulty network portion. According to the disclosed technique, the message route is designated by the message-originating processor inserting routing bits into its message.